package demo1;

import java.util.Arrays;

public class Test3 {
    public static void main(String[] args) {
        int[] array = {12 , 3, 50 , 33 , 21 , 20 , 17 , 15 , 9} ;   // 定义一个数组供我们排序 ;
         quickSort(array);
        System.out.println(Arrays.toString(array)); // 查看排序后的结果 ;
    }
    // 快速排序方法 ;
    public static void quickSort(int[] array)  {  //  传一个数组,即可排序
       quick(array , 0 , array.length-1);   // 数组区间时 [0 , length-1]
    }
    // 找基准 , left和right 开始 互相找元素, 直到相遇 ;
    private static int partitionHoare(int[] array , int left , int right){       // partition是划分的意思 ,Hoare 是快速排序的提出者,表示我们用的是Hoare版本的快速排序
          int key = array[left] ;       // 以区间第一个元素作为key ,
           int keyIndex = left ;        // 记录 key 的下标 ;
        while(left < right){       //left和right相遇就停止
            while(left < right && key <= array[right]){  // right从右开始, 找小于key的元素 ;
                right -- ;
            }
            while(left < right && key >= array[left]){   // left 从左开始, 找 大于key的元素 ;
                left ++ ;
            }
            swap(array , left , right);             //交换left和right指向的元素
        }
        swap(array , keyIndex , left);     // left和right相遇的地方,就是pivot , 交换pivot所指的元素 和 key
        return  left ;       // left和right最后的位置,就是pivot;  返回pivot;
    }
    // 找到基准后 , 用基准pivot 来递归 左右区间 ;
    private static void quick(int[] array , int left , int right){
        // 如果left 和 right 相遇 表示 区间只有一个元素 ,就直接返回 ;
        if(left >= right) return;
        // 根据 该区间获取 pivot基准
        int pivot = partitionHoare(array , left , right) ; // 获得基准 :
        // 根据基准递归 ;
        // 递归 pivot 左边的区间 ; 因为我们是靠 left 和right 求的基准 , 所以 用left和right 配合pivot 划分左右区间
        quick(array , left , pivot-1);   // 左边区间是 [left , pivot-1]

        //递归 pivot 右边区间
        quick(array , pivot+1 , right);  // 右边区间时 [pivot+1 , right]
    }
    //交换数组元素位置的方法
    private static void swap(int[] array , int x , int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp ;
    }
}
